
//456.132模式
class Solution {
public:
    bool find132pattern(vector<int>& nums) {
        //枚举中间位置j,向两边找满足条件的位置
        //维护找j左边的最小值O(1)
        //在j右边找比左边最小值大的位置,可以使用set存储右边的值,查找就是O(logN)
        int n=nums.size();
        multiset<int> rs;    //不能使用set
        for(int i=2;i<n;i++) 
            rs.insert(nums[i]);
        int lmin=nums[0];

        for(int i=1;i<n-1;i++)
        {
            if(nums[i]>lmin) 
            {
                auto it=rs.upper_bound(lmin);
                if(it!=rs.end()&&*it<nums[i]) return true;
            }
            
            lmin=min(lmin,nums[i]);
            rs.erase(rs.find(nums[i+1]));  //只删除rs中的一个nums[i]
        }
        return false;
    }
};